package com.ocean.array;

/**
 * https://leetcode.cn/problems/climbing-stairs/
 */
public class ClimbStairs {


    public static void main(String[] args) {
        System.out.println(new ClimbStairs().climbStairs4(2));
        System.out.println(new ClimbStairs().climbStairs4(3));
        System.out.println(new ClimbStairs().climbStairs4(4));
        System.out.println(new ClimbStairs().climbStairs4(5));
        System.out.println(new ClimbStairs().climbStairs4(6));
        System.out.println(new ClimbStairs().climbStairs4(7));
    }

    public int climbStairs(int n) {
        int q = 0;
        int p = 0;
        int r = 1;
        /**
         * 为什么从1开始 到n结束？
         * f(1) = f(0) +0
         * f(2) = f(1) + f(0)
         * f(3) = f(2) +f(1)
         * f(4) = f(3) +f(2)
         * f(5) = f(4) +f(3)
         * 按照上面的表达式 到n应该计算n次
         *
         */
        for (int i = 1; i <= n; i++) {
            q = p;  // q 等于上上次的结果
            p = r;  // p 等于第上次的结果
            r = q + p; // r 等于这次的结果
        }
        return r;
    }


    public int climbStairs2(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int q = 1;
        int p = 2;
        int r = 3;
        for (int i = 3; i < n; i++) {
            q = p;
            p = r;
            r = q + p;
        }
        return r;
    }

    public int climbStairs3(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;
        for (int i = 2; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }


    public int climbStairs4(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return climbStairs4(n - 1) + climbStairs4(n - 2);
    }

}
